/**
 * Implementation of the model percolation.
 * @author Ailen
 *
 */

public class Percolation {
	//Instance of weighted quick union. 
	private WeightedQuickUnionUF uf;
	//size of the grid.
    private int size;
    //the 2-dimensions boolean grid to record the open states of each cell.
    private boolean[][] grid;
    /**
     * Create N-by-N grid, with all sites blocked
     * @param N -- dimensional size of the grid.
     */
    public Percolation(int N){
        this.size = N;
        this.grid = new boolean[this.size][this.size];
        for (int r = 0; r < this.size; r++)
        {
            for (int c = 0; c < this.size; c++)
            {
                this.grid[r][c] = false;
            }
        }
        this.uf = new WeightedQuickUnionUF(this.size * this.size);
    }
    
    /**
     * Open the site located at (i, j).
     * @param i -- index of row, 1 to N.
     * @param j -- index of column, 1 to N.
     */
    public void open(int i, int j)
    {
        if (i < 1 || j < 1 || i > this.size || j > this.size)
            throw new IndexOutOfBoundsException();
        if (this.grid[i - 1][j - 1])
        	return;
        //open this cell.
        this.grid[i - 1][j - 1] = true;
        //union the cells around the new opened one.
        System.out.println(i + " " + j);
        if (i - 1 > 0 && this.isOpen(i - 1, j))
        {
        	this.uf.union(this.indexTrans(i - 1, j - 1), this.indexTrans(i - 2, j - 1));
        }
        if (j - 1 > 0 && this.isOpen(i, j - 1))
        {
        	this.uf.union(this.indexTrans(i - 1, j - 1), this.indexTrans(i - 1, j - 2));
        }
        if (i < this.size && this.isOpen(i + 1, j))
        {
        	this.uf.union(this.indexTrans(i - 1, j - 1), this.indexTrans(i, j - 1));
        }
        if (j < this.size && this.isOpen(i, j + 1))
        {
        	this.uf.union(this.indexTrans(i - 1, j - 1), this.indexTrans(i - 1, j));
        }
    }
    
    /**
     * Get whether the site is opened.
     * @param i -- index of row.
     * @param j -- index of column.
     * @return  true for open; false otherwise.
     */
    public boolean isOpen(int i, int j)
    {
        if (i < 1 || j < 1 || i > this.size || j > this.size)
            throw new IndexOutOfBoundsException();
        return this.grid[i - 1][j - 1];
    }
    
    /**
     * Translate the index of 2-dimensions to the index of array.
     * @param row	-- index of row, 0 to N - 1.
     * @param column	-- index of column, 0 to N - 1.
     * @return	index represented in 1-dimension array.
     */
    private int indexTrans(int row, int column)
    {
    	return (column - 1) + (row - 1) * this.size;
    }
    
    /**
     * Is the site full? 
     * @param i	-- index of row.
     * @param j	-- index of column.
     * @return	true for full; false otherwise.
     */
    public boolean isFull(int i, int j)
    {
        if (i < 1 || j < 1 || i > this.size || j > this.size)
            throw new IndexOutOfBoundsException();
        //what does "full" mean here?
        return !this.grid[i-1][j-1];
    }
    
    /**
     * Does the system percolate?
     * @return  true for percolation; false otherwise.
     */
    public boolean percolates()
    {
    	for (int cTop = 1; cTop <= this.size; cTop++)
    	{
    		for (int cBot = 1; cBot <= this.size; cBot++)
    		{
    			if (this.uf.connected(this.indexTrans(1, cTop), this.indexTrans(this.size, cBot)))
    				return true;
    		}
    	}
    	return false;
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
    	Percolation demo = new Percolation(4);
    	for (int i = 1; i <= 4; i++)
    	{
    		demo.open(i, 1);
    	}
    	for (int i = 0; i < 4; i++)
    	{
    		for (int j = 0; j < 4; j++)
    		{
    			System.out.println("grid[" + i + "][" + j + "] -- " + demo.grid[i][j]);
    		}
    	}
    	System.out.println(demo.percolates());
    }

}
